<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            // 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
            list1 = [1, 2, 3, 0, 0, 0];
            list2 = [4, 5, 6];
            // 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
            // 输出：[1,2,2,3,5,6]
            // 解释：需要合并 [1,2,3] 和 [2,5,6] 。
            // 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

            // 来源：力扣（LeetCode）
            // 链接：https://leetcode-cn.com/problems/merge-sorted-array
            // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

            var merge1 = function (nums1, m, nums2, n) {
                nums1.splice(m, nums1.length - m, ...nums2);
                nums1.sort((a, b) => a - b);
                return nums1;
            };

            // 双指针
            // 复杂度分析
            // 时间复杂度：O(m+n)O(m+n)。
            // 指针移动单调递增，最多移动 m+nm+n 次，因此时间复杂度为 O(m+n)O(m+n)。
            // 空间复杂度：O(m+n)O(m+n)。
            // 需要建立长度为 m+nm+n 的中间数组 \textit{sorted}sorted。
            var merge2 = function (nums1, m, nums2, n) {
                let p1 = 0,
                    p2 = 0;
                const sorted = new Array(m + n).fill(0);
                var cur;
                while (p1 < m || p2 < n) {
                    if (p1 === m) {
                        cur = nums2[p2++];
                    } else if (p2 === n) {
                        cur = nums1[p1++];
                    } else if (nums1[p1] < nums2[p2]) {
                        cur = nums1[p1++];
                    } else {
                        cur = nums2[p2++];
                    }
                    sorted[p1 + p2 - 1] = cur;
                }
                for (let i = 0; i != m + n; ++i) {
                    nums1[i] = sorted[i];
                }
                return nums1;
            };

            // 逆向双指针
            // 时间复杂度：O(m+n)O(m+n)。
            // 指针移动单调递减，最多移动 m+nm+n 次，因此时间复杂度为 O(m+n)O(m+n)。
            // 空间复杂度：O(1)O(1)。
            // 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
            var merge3 = function (nums1, m, nums2, n) {
                let p1 = m - 1,
                    p2 = n - 1;
                let tail = m + n - 1;
                var cur;
                while (p1 >= 0 || p2 >= 0) {
                    if (p1 === -1) {
                        cur = nums2[p2--];
                    } else if (p2 === -1) {
                        cur = nums1[p1--];
                    } else if (nums1[p1] > nums2[p2]) {
                        cur = nums1[p1--];
                    } else {
                        cur = nums2[p2--];
                    }
                    nums1[tail--] = cur;
                }
                return nums1;
            };

            console.log(merge1(list1, 3, list2, 3));
            console.log(merge2(list1, 3, list2, 3));
            console.log(merge3(list1, 3, list2, 3));
        </script>
    </body>
</html>
